package com.leetcode.problems035;

/**
 * https://leetcode-cn.com/problems/search-insert-position/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public int searchInsert(int[] nums, int target) {
        int i = floor(nums,target);
        if(i == -1){
            return 0;
        }
        if(nums[i] == target){
            return i;
        }
        return i + 1;
    }

    /**
     * 小于等于target的第一个数的下标
     * @param nums
     * @param target
     * @return
     */
    public int floor(int[] nums, int target){
        int l = 0;
        int r = nums.length - 1;
        int ans = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid - 1;
            }else{
                l = mid + 1;
                ans = mid;
            }
        }
        if(ans + 1 < nums.length && nums[ans + 1] == target){
            return ans + 1;
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6};
        System.out.println(new Solution().searchInsert(nums,8));
    }
}
